package com.qimingyu.recursion;

import java.util.Arrays;

/**
 * @author doreaxon
 * @version 1.0
 * @date 2023/9/9 14:24
 * @注释 递归实现插入排序
 *
 * 思路是用一个边界（初始时是索引1，因为左边只有一个数字，一个数字天然有序）把数组划分成两个区域，左边为有序区域，右边（包括边界）为无序区域
 * 每次选右边的无序区域中的第一个数字（即边界）向左比较
 */
public class InsertionSortWithRecursion {

    // 插入排序的递归实现
    public static void insertionSort(int[] arr) {
        // 如果数组长度为1，直接返回
        if (arr.length == 1) {
            return;
        }
        // 初始化low为1
        int low = 1;
        // 调用递归方法对数组进行排序
        insertionSortWithRecursion(arr, low);
    }

    // 插入排序的递归方法
    public static void insertionSortWithRecursion(int[] arr, int low) {
        // 如果low等于数组长度，说明已经处理完所有元素，直接返回
        if (low == arr.length) {
            return;
        }
        // 获取当前位置的值
        int lowValue = arr[low];
        // 初始化i为low-1
        int i = low - 1;
        // 当i大于等于0且lowValue小于arr[i]时，将arr[i]向后移动一位
        while (i >= 0 && lowValue < arr[i]) {
            arr[i + 1] = arr[i];
            i--;
        }
        // 将lowValue插入到正确的位置
        arr[i + 1] = lowValue;
        // 递归处理下一个位置
        insertionSortWithRecursion(arr, low + 1);
    }

    // 主方法，用于测试插入排序算法
    public static void main(String[] args) {
        // 定义一个待排序的数组
        int[] arr = new int[]{1, 9, 2, 5, 0, 10, 7};
        // 调用插入排序方法对数组进行排序
        insertionSort(arr);
        // 输出排序后的数组
        System.out.println(Arrays.toString(arr));
    }
}
